"""P3 3.认识O(NlogN)的排序"""

from random import random


def get_max(arr: list, left: int, right: int):
    """二分法获取列表中的最大值"""
    if left == right:
        return arr[left]
    # N >> 1 表示 N // 2
    mid = left + ((right - left) >> 1)
    left_max = get_max(arr, left, mid)
    right_max = get_max(arr, mid + 1, right)
    return left_max if left_max > right_max else right_max


"""
master公式：
T(N) = a * T(N / b) + O(N^d)
1、log(b, a) < d 复杂度为O(N^d)
2、log(b, a) > d 复杂度为O(N^log(b, a))
3、log(b, a) = d 复杂度为O(N^d * log(2, N))
"""


def merge_sort(arr: list, left: int, right: int) -> None:
    """归并排序，时间复杂度O(N * log(2, N))，额外空间复杂度O(N)"""
    if left == right:
        return
    mid = left + ((right - left) >> 1)
    merge_sort(arr, left, mid)
    merge_sort(arr, mid + 1, right)
    # 归并两个有序数组的过程
    p1, p2 = left, mid + 1
    help_array = list()
    while p1 <= mid and p2 <= right:
        # 相等时放入p1的值，使算法具备稳定性
        if arr[p1] <= arr[p2]:
            help_array.append(arr[p1])
            p1 += 1
        else:
            help_array.append(arr[p2])
            p2 += 1
    while p1 <= mid:
        help_array.append(arr[p1])
        p1 += 1
    while p2 <= right:
        help_array.append(arr[p2])
        p2 += 1
    for i in range(left, right + 1):
        arr[i] = help_array[i - left]


def small_sum(arr: list, left: int, right: int) -> int:
    """
    小和问题。
    在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和
    """
    if left == right:
        return 0
    mid = left + ((right - left) >> 1)
    left_sum = small_sum(arr, left, mid)
    right_sum = small_sum(arr, mid + 1, right)
    # 合并过程中也可能产生小和
    p1, p2, merge_sum = left, mid + 1, 0
    help_array = list()
    while p1 <= mid and p2 <= right:
        if arr[p1] < arr[p2]:
            merge_sum += (arr[p1] * (right - p2 + 1))
            help_array.append(arr[p1])
            p1 += 1
        else:
            help_array.append(arr[p2])
            p2 += 1
    while p1 <= mid:
        help_array.append(arr[p1])
        p1 += 1
    while p2 <= right:
        help_array.append(arr[p2])
        p2 += 1
    for i in range(left, right + 1):
        arr[i] = help_array[i - left]
    return left_sum + right_sum + merge_sum


def quick_sort(arr: list, left: int, right: int) -> None:
    """随机快速排序，时间复杂度O(N * log(2, N))，额外空间复杂度O(log(2, N))"""
    random_index = int(random() * (right - left + 1)) + left
    arr[random_index], arr[right] = arr[right], arr[random_index]
    # 将数组划分为三部分
    less, i, more = left - 1, left, right
    while i < more:
        if arr[i] < arr[right]:
            less += 1
            arr[less], arr[i] = arr[i], arr[less]
            i += 1
        elif arr[i] > arr[right]:
            more -= 1
            arr[more], arr[i] = arr[i], arr[more]
        else:
            i += 1
    arr[more], arr[right] = arr[right], arr[more]
    if less >= left:
        quick_sort(arr, left, less)
    if more < right:
        quick_sort(arr, more + 1, right)


if __name__ == "__main__":
    array = [4, 5, 8, 1, 3]
    # print(get_max(array, 0, len(array) - 1))
    # merge_sort(array, 0, len(array) - 1)
    # print(array)
    # print(small_sum(array, 0, len(array) - 1))
    quick_sort(array, 0, len(array) - 1)
    print(array)
